# -*- coding: utf-8 -*-
# @Time    : 2020/11/8 15:22
# @Author  : DuJiabao
# @File    : MaxSubsequenceSum.py
# @Description : this is a program to calculate the max sum of a sub sequence in a sequence.最大子序列和

def MaxSubsequenceSum1(A):
    """
    方法1
    缺点：无法应对纯负数情景
    :param A:序列
    :return: 最大子序列和
    """
    MaxSum, ThisSum = 0, 0
    for item in A:
        ThisSum += item
        if ThisSum > MaxSum:
            MaxSum = ThisSum
        elif ThisSum < 0:
            ThisSum = 0
    return MaxSum


def MaxSubsequenceSum2(A):
    """
    方法2
    :param A: 序列
    :return: 最大子序列和
    """
    for i in range(1, len(A)):
        A[i] += max(A[i - 1], 0)
    return max(A)


if __name__ == '__main__':
    A = [4, -3, 5, -2, -1, 2, 6, -2]
    print(MaxSubsequenceSum1(A))
    print(MaxSubsequenceSum2(A))
